#include <iostream>
#include <sstream>
#include <map>
#include <set>

using namespace std;

int record = 999999999;

struct point {
    bool allocated;
    set <int> nb; // neighbours
};
map <int, struct point> pp;

static int get_delta(const struct point &p)
{
    int delta = 0;
    for (set<int>::const_iterator it = p.nb.begin(); it != p.nb.end(); it++) {
        if (pp[*it].allocated)
            --delta;
        else
            ++delta;
    }
    return delta;
}

static void search(int deep, int cur_width, int max_width)
{
    if (deep > 0) {
        map <int, struct point>::iterator it = pp.begin();
        for (; it != pp.end() && max_width < record; it++) {
            struct point &p = it->second;
            if (p.allocated) continue;
            int const new_width = cur_width + get_delta(p);
            p.allocated = true;
            search(deep - 1, new_width, max(new_width, max_width));
            p.allocated = false;
        }
    } else {
        if (max_width < record) {
            record = max_width;
            cout << ": " << record << endl;
        }
    }
}

static void create()
{
    unsigned int a, b;
    std::string line;
    while (std::getline(std::cin, line) && !line.empty()) {
        std::stringstream ss(line);
        ss >> a >> b;
        pp[a].nb.insert(b);
        pp[b].nb.insert(a);
    }
}

static void print()
{
    map <int, struct point>::iterator it = pp.begin();
    for (; it != pp.end(); it++) {
        cout << it->first << ":";
        set<int>::iterator ipp = it->second.nb.begin();
        for (; ipp != it->second.nb.end(); ipp++) {
            cout << " " << *ipp;
        }
        cout << endl;
    }
}

int main()
{
    create();
#if 0
    print();
#endif
    search(pp.size() - 1, 0, 0);
    return 0;
}


